Tute (Week 5)

1. No it is not true, consider for example \(\varphi = p\) and \(\psi=q\) (where \(p\) and \(q\) are propositional variables). Then neither \(P \models Q\) nor \(P \models \neg Q\).
2. Not true either. For example, let \(\varphi = (x = y)\) and \(\psi = (z = w)\).

We need to find a model where the first formula holds but the second does not.

Consider a model \(\mathcal{M}\) where the domain has one element, where \(P^\mathcal{M} = \emptyset\) and \(Q^\mathcal{M} = \emptyset\). Then \([\![\forall x (P(x) \rightarrow Q(x))]\!]_\mathcal{M}\) holds (the implication becomes vacuously true). But \([\![\exists x Q(x)]\!]_\mathcal{M}\) does not.

We can use natural deduction: \[ \dfrac { \dfrac {\forall x P(x)} {P(c)} \forall\mbox{-E} } {\exists x P(x)} \exists\mbox{-I} \]

We could also try a direct semantic argument, but this is considerably more involved.

Natural deduction becomes unsound for an empty domain of discourse. For example, consider \(\forall\mbox{-E}\): \[ \dfrac {\forall x P(x)} {P(c)} \]

If the domain of discourse is empty, the premise of this rule is vacuously true: everything in the domain of discourse does indeed satisfy \(P\). But the conclusion is false (or ill-formed, if you prefer): \(P(c)\) cannot hold because there is no \(c\).

You can use similar arguments to show breakdowns of useful logical laws. For example, the law \[ \exists x. \top \equiv \top \]

would fail in an empty domain of discourse.

1. Yes. Peano arithmetic is one possible model of our vocabulary, and \(\models \varphi\) means that \(\varphi\) is true in every possible model (and environment).
2. No. \(\not\models \varphi\) means that \(\varphi\) is false in at least one model, but it may still be true in Peano arithmetic. For example, the formula \({\tt S}({\tt Z}) = {\tt Z}\) is false in Peano arithmetic, but true in any model with a one-element domain of discourse.

3. The first two Peano axioms are more syntax than semantics, and hence do not require any FOL axioms. For example, "there is a number \({\tt Z}\)" follows immediately from the fact that \({\tt Z}\) is in the vocabulary. For axioms 3 and 4 we can do the following:

   \begin{array}{l} \{\forall n(\neg({\tt S}(n) = {\tt Z})), \\ \ \ \forall n \forall m({\tt S}(n) = {\tt S}(m) \ \ \rightarrow\ \ n = m) \} \end{array}

4. Using logical notation instead of set notation, the induction axiom can be stated as: \[\forall P((P({\tt Z}) \wedge \forall n(P(n) \rightarrow P({\tt S}(n)))) \rightarrow \forall n(P(n)))\] Unfortunately, the above is not a wff in first-order predicate logic! That's because first-order logic only allows quantification over (term) variables. \(P\), however, is not a term variable but a predicate symbol.

   What we can do is add an infinite family of instances of the induction axiom to our theory. The idea is that for every wff \(\varphi(n)\), we add an axiom \[(\varphi({\tt Z}) \wedge \forall n(\varphi(n) \rightarrow \varphi({\tt S}(n)))) \rightarrow \forall n(\varphi(n))\] This approach allows us to do Peano arithmetic for most practical purposes, but will still not uniquely characterise Peano arithmetic: there will be other models that also satisfy these axioms. This is a bit beyond the scope of the course, but if you're interested in why, look up the compactness theorem and non-standard models of arithmetic. One place to start is here.